// 希尔排序
// 时间复杂度 O(nlog2n) 空间 O(1) 内排 不稳定
function shellSort(arr) {
    let gap = 4;
    while(gap > 1) {
        gap = gap/2;
        do{
            falg = 0 // falg 为0，表示无元素交换
            for(i = 0; i < arr.length - gap; i++) {
                let j = i + gap;
                if(arr[i] > arr[j]) {
                   let temp = arr[i];
                   arr[i] = arr[j],
                   arr[j] = temp;
                    falg = 1; // 令falg为1 表示有元素交换
                }
            }
        } while(falg != 0)
    }
    return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));